1. Field of the Invention
The present invention relates to an encryption processing apparatus, an encryption processing method, and a computer program. More particularly, the present invention relates to an encryption processing apparatus for realizing high-speed computation of the scalar double-and-add point kP+lQ in elliptic curve cryptography and the scalar double-and-add divisor kD1+lD2 in hyperelliptic curve cryptography, an encryption processing method for use therewith, and a computer program for use therewith.
2. Description of the Related Art
As network communication and electronic commerce have progressed in recent years, ensuring security in communication has- become an important issue. An example of a security ensuring method is encryption technology. At present, communication using various encryption techniques has been performed.
A system has been put into practical use in which, for example, an encryption processing module is embedded in a small device, such as an IC card, data transmission/reception is performed between the IC card and a reader/writer serving as a data reading/writing device, and an authentication process or encryption and decryption of transmission/reception data are performed.
For example, IC cards with which an encryption process is performed have come to be increasingly used in various gates such as ticket gates of stations or in shopping centers. There has been a stringent demand for miniaturization and high processing speed.
Encryption is broadly classified into a common key encryption method and a public key encryption method. The common key encryption method is also called a symmetrical encryption method, and both a transmitting party and a receiving party possess a common key. Examples of the common key encryption method include that according to DES (Data Encryption Standard). Features of the DES algorithm are that encryption and decryption can be performed by almost the same algorithm.
In contrast with the common key encryption method, the configuration in which the key of the transmitting party is made different from the key of the receiving party is a public key encryption method or an asymmetrical encryption method. In the public key encryption method, unlike the common key encryption method in which a common key is used for encryption and decryption, a secret key should only be possessed by one person, and therefore, this is advantageous in the management of keys. However, the data processing speed of the public key encryption method is slower than that of the common key encryption method, and in general, the public key encryption method is often used for objects with a small amount of data, such as delivery of a secret key and a digital signature. As examples of public key encryption methods, RSA (Rivest-Shamir-Adleman) cryptography and elliptic curve cryptography (ECC) are known.
Elliptic curve cryptography is cryptography using the difficulty of solving a discrete logarithm problem on an elliptic curve, and is said to have security equivalent to that of 1024-bit RSA encryption at 160 bits. In general, in elliptic curve cryptography, an elliptic curve: y2=x3+ax+b(4a3+27b2≠0) on a prime field, an elliptic curve: y2+xy=x3+ax2+b (b≠0) on an extension field of two, and the like are used. A set in which a point at infinity (O) is added to points on these curves forms a finite group with regard to the addition, and the point at infinity (O) forms the unity thereof. Hereinafter, the addition of points in the finite group is denoted by +.
This addition P+Q of two different points P and Q in the finite group is referred to as “point addition”, and the addition P+P=2P of a point P and a point P is referred to as “point doubling”.
Furthermore, computation for determining a point P+P+ . . . +P=kP in which a point P is added k times is referred to as “scalar point multiplication”. Computation in elliptic curve cryptography is described in, for example, D. Hankerson, J. L. Hernandez, and A. Menezes, “Software Implementation of Elliptic Curve Cryptography over Binary Fields”, Cryptographic Hardware and Embedded Systems—CHES 2000, LNCS 1965, pp. 1-24, Springer-Verlag, 2000.
Furthermore, a “simultaneous scalar point multiplication algorithm” for computing the scalar double-and-add point kP+lQ of two different points P and Q on an elliptic curve at a high speed is known. k and l are each given by a scalar quantity. The simultaneous scalar point multiplication algorithm is performed by using an algorithm with each of the scalar values k and l being expressed in a binary representation ask=(kn . . . k0)2 andl=(ln . . . l0)2.“Simultaneous Scalar Point Multiplication Algorithm”                Input: Points P and Q on an elliptic curve                    Scalar values k and l                        Output: kP+lQ        1. Compute P+Q        2. T←(knP+lnQ)        3. For i=n−1 downto 0 do                    T←2T            If (ki, li)≠(0, 0) then                            T←T+(kiP+liQ)                                                4. Return T        
The “simultaneous scalar point multiplication algorithm” is a technique in which kP and lQ as individual scalar multiplications of each of points P and Q are not computed separately, but kP+lQ is simultaneously computed on the basis of the conditions of corresponding bits (ki, li) of the binary representation scalar quantity. In this technique, the number of times point doubling is performed can be reduced to approximately half that of the case in which scalar multiplication of kP or lQ of each point P or Q is computed and thereafter kP+lQ is performed as a point addition process, thereby realizing higher speed.
While encryption utilizing the difficulty of solving a discrete logarithm problem on an elliptic curve exists, an attack method called power analysis attack that reveals secret information stored in a device by measuring the power consumption of the device in the middle of an elliptic curve cryptography process has been proposed. Power analysis attack includes mainly simple power analysis (SPA) using one power consumption waveform and differential power analysis (DPA) using differences between power consumption waveforms. A power analysis attack on elliptic curve cryptography is described in, for example, J. -S. Coron, “Resistance against Differential Power Analysis for Elliptic Curve Cryptosystems”, Cryptographic Hardware and Embedded System-CHES'99, LNCS 1965, pp. 292-302, Springer-Verlag, 1999. In general, countermeasures against DPA in elliptic curve cryptography are realized by combining a randomizing technique with countermeasures against SPA.
However, the “simultaneous scalar point multiplication algorithm” is not safe for SPA. Since computations of point doubling and point addition are performed as different processes, features of power consumption in the middle of computation differ. Therefore, it is possible for an attacker to distinguish whether point doubling is being performed or point addition is being performed by viewing a power consumption waveform.
In step 3 in the above “simultaneous scalar point multiplication algorithm”, whereas point doubling of T←2T is performed on all i, point addition of T←T+(kiP+liQ) is performed only when (ki, li)≠(0, 0). Therefore, it is possible for the attacker to distinguish whether (ki, li)=(0, 0) by viewing a power consumption waveform. In the above “simultaneous scalar point multiplication algorithm”, pre-computation of performing point addition of P+Q in step 1 is necessary.